package jm.data.structure.heap;

import jm.data.structure.tree.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @Description 二叉堆实现
 * @date 2022/4/29 9:38
 */
public class BinaryHeap<E> implements Heap<E>, BinaryTreeInfo {

    // 存储元素的数组
    private E[] es;
    // 元素数量
    private int size;
    // 比较器
    private Comparator<E> comparator;
    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(Comparator<E> comparator){
        this.comparator = comparator;
        this.es = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public BinaryHeap(){
        this(null,null);
    }

    public BinaryHeap(E[] es, Comparator<E> comparator){
        this.comparator = comparator;
        if (es == null || es.length == 0){
            this.es = (E[]) new Object[DEFAULT_CAPACITY];
        }else {
            size = es.length;
            int capacity = Math.max(es.length,DEFAULT_CAPACITY);
            this.es = (E[]) new Object[capacity];
            for (int i = 0; i < es.length; i++) {
                this.es[i] = es[i];
            }
            heapify();
        }
    }

    public BinaryHeap(E[] es){
        this(es,null);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        for (E e : es) {
            e = null;
        }
        size = 0;
    }

    @Override
    public void add(E e) {
        elementNotNullCheck(e);
        ensureCapacity(size + 1);
        es[size++] = e;
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return es[0];
    }

    @Override
    public E remove() {
        emptyCheck();
        int lastIndex = --size;
        E root = es[0];
        es[0] = es[lastIndex];
        es[lastIndex] = null;
        siftDown(0);
        return root;
    }

    @Override
    public E replace(E e) {
        elementNotNullCheck(e);
        E root = es[0];
        if (size == 0){
            es[0] = e;
            size = 1;
        }else {
            // 替换堆顶
            es[0] = e;
            siftDown(0);
        }
        return root;
    }

    /**
     * 批量创堆
     */
    private void heapify(){
//        // 自上而下的上滤
//        for (int i = 1; i < size; i++) {
//            siftUp(i);
//        }

        // 自下而上的下滤
        for (int i = (size >> 1) - 1 ; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index){
        E e = es[index];
        // 计算出非叶子节点数量
        int half = size >> 1;
        while (index < half){
            // 因为可能没有右子节点，默认使用右子节点
            int childIndex = (index << 1) + 1;
            E child = es[childIndex];
            // 获取右子节点
            int rightIndex = childIndex + 1;
            if (rightIndex < size && compare(es[rightIndex],child) > 0){
                childIndex = rightIndex;
            }
            if (compare(e,child) >= 0){
                break;
            }
            es[index] = child;
            index = childIndex;
        }
        es[index] = e;
    }

    /**
     * 上滤
     * @param index
     */
    private void siftUp(int index){
        E e = es[index];
        while (index > 0){
            int parentIndex = (index - 1) >> 1;
            E parent = es[parentIndex];
            if (compare(e,parent) <= 0){
                break;
            }
            // 将父元素放到index位置；
            es[index] = parent;
            // 将index变为父节点的索引值
            index = parentIndex;
        }
        // 将新节点放到父节点位置
        es[index] = e;
    }

    /**
     * 元素比较
     * @param e
     * @param e1
     * @return
     */
    private int compare(E e, E e1){
        return comparator != null ? comparator.compare(e,e1)
                : ((Comparable)e).compareTo(e1);
    }

    /**
     * 空堆检测
     */
    private void emptyCheck(){
        if (size == 0){
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }

    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = es.length;
        if (oldCapacity >= capacity){
            return;
        }
        // 变成原先容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = es[i];
        }
        es = newElements;
    }

    /**
     * 空 e 检测
     * @param e
     */
    private void elementNotNullCheck(E e){
        if (e == null){
            throw new IllegalArgumentException("E must be not null");
        }
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index =  (Integer) node;
        index = (index << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        int index =  (Integer) node;
        index = (index << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        int index =  (Integer) node;
        return es[index];
    }
}
